`
https://leetcode.cn/problems/split-array-largest-sum/
`

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var splitArray = function (nums, k) {
  // 将题目换一个角度看

  // 你只有一艘货船，现在有若干货物，每个货物的重量是 nums[i]
  // 现在你需要在 m 天内将这些货物运走，请问你的货船的最小载重是多少？

  // 货船每天运走的货物就是 nums 的一个子数组；
  // 在 m 天内运完就是将 nums 划分成 m 个子数组；
  // 让货船的载重尽可能小，就是让所有子数组中最大的那个子数组元素之和尽可能小
  return shipWithinDays(nums, k)
};

// 1011. 在 D 天内送达包裹的能力
// https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/
var shipWithinDays = function (weights, days) {
  let left = 0, right = 0
  for (let w of weights) {
    left = Math.max(left, w);
    right += w;
  }
  const f = (x) => {
    let needDay = 0;
    for (let i = 0; i < weights.length;) {
      let cap = x;
      while (i < weights.length) {
        if (cap < weights[i])
          break;
        else
          cap -= weights[i];
        i++;
      }
      needDay++;
    }
    return needDay;
  }

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2)
    const cur = f(mid)
    if (cur > days) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  return left
};